package com.czh.queue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 队列操作: 是一种遵循先入先出规则的线性数据结构
 *
 * @author chenzhihua
 * @Date 2024/2/20
 */
public class BaseOperateQueue {
    public static void main(String[] args) {
        //1. java自带的队列对象实现===LinkedList也可以实现双向队列
        System.out.println("使用java自带的队列操作===");
        javaQueue();
        //2. 基于链表实现的队列
        System.out.println("使用链表实现的队列操作===");
        linkNodeQueue();
        //3. 基于环形数组实现的队列
        System.out.println("使用环形数组实现的队列操作===");
        ringQueue();
    }

    //1. java自带的队列对象实现
    private static void javaQueue() {
        Queue<Integer> queue = new LinkedList<>();
        // 1. 入队
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        // 2. 获取队列头
        Integer peek = queue.peek();
        System.out.printf("队列头元素是: %d\n", peek);
        // 3. 出队
        Integer pop = queue.poll();
        System.out.printf("出队元素是: %d\n", pop);
        // 4. 获取队列长度
        int size = queue.size();
        System.out.printf("队列长度: %d\n", size);
        // 5. 判断是否是空队列
        boolean empty = queue.isEmpty();
        System.out.println("队列是否为空:" + empty);
    }

    // 基于链表实现的队列
    private static void linkNodeQueue() {
        ListNodeQueue listNodeQueue = new ListNodeQueue();
        //1. 入队列
        listNodeQueue.offer(1);
        listNodeQueue.offer(2);
        listNodeQueue.offer(3);
        listNodeQueue.offer(4);
        listNodeQueue.offer(5);
        //2. 获取队列顶元素
        int peek = listNodeQueue.peek();
        System.out.printf("队列顶元素是: %d\n", peek);
        // 3. 出队列
        int pop = listNodeQueue.poll();
        System.out.printf("出队列元素是: %d\n", pop);
        // 4. 获取队列长度
        int size = listNodeQueue.size();
        System.out.printf("队列长度: %d\n", size);
        // 5. 判断是否是空队列
        boolean empty = listNodeQueue.isEmpty();
        System.out.println("队列是否为空:" + empty);
    }

    //3. 基于环形数组实现的队列
    private static void ringQueue() {
        RingQueue ringQueue = new RingQueue(5);
        //1. 入队列
        ringQueue.offer(1);
        ringQueue.offer(2);
        ringQueue.offer(3);
        ringQueue.offer(4);
        ringQueue.offer(5);
        //2. 获取队列顶元素
        int peek = ringQueue.peek();
        System.out.printf("队列顶元素是: %d\n", peek);
        // 3. 出队列
        int pop = ringQueue.poll();
        System.out.printf("出队列元素是: %d\n", pop);

        ringQueue.offer(5);
        ringQueue.poll();
        ringQueue.poll();
        ringQueue.poll();
        ringQueue.poll();
        int pop1 = ringQueue.poll();
        System.out.printf("出队列元素是: %d\n", pop1);

        // 4. 获取队列长度
        int size = ringQueue.size();
        System.out.printf("队列长度: %d\n", size);
        // 5. 判断是否是空队列
        boolean empty = ringQueue.isEmpty();
        System.out.println("队列是否为空:" + empty);
    }
}

/* 基于链表实现的队列 */
class ListNodeQueue {
    ListNode front, real; // 队列头和队列尾
    int size;

    public ListNodeQueue() {
        front = null;
        real = null;
        size = 0;
    }

    // 入队列
    public void offer(int val) {
        ListNode node = new ListNode(val);
        // 如果队列为空，则头和尾节点都指向该节点
        if (isEmpty()) {
            front = node;
            real = node;
        } else {
            // 如果队列不为空，则将该节点添加到尾节点后
            real.next = node;
            real = node;
        }
        size++;
    }

    // 获取队列头
    public int peek() {
        return front.val;
    }

    // 出队列
    public int poll() {
        // 获取队列头进行返回
        int peek = peek();
        // 队列头后移一个
        front = front.next;
        size--;
        return peek;
    }

    // 获取队列长度
    public int size() {
        return size;
    }

    // 判断是否是空
    public boolean isEmpty() {
        return size() == 0;
    }
}

class ListNode {
    int val;
    ListNode next;

    // 构造函数
    public ListNode(int val) {
        this.val = val;
    }

    public ListNode() {
    }
}


/* 基于环形数组实现的队列 */
class RingQueue {
    int[] nums;
    int front; // 队列头
    int size;

    public RingQueue(int capacity) {
        nums = new int[capacity];
        front = size = 0;
    }

    /* 获取队列的容量 */
    public int capacity() {
        return nums.length;
    }

    // 入队列
    public void offer(int val) {
        if (isFull()) return;
        nums[(front + size) % capacity()] = val;
        size++;
    }

    // 获取队列头
    public int peek() {
        return nums[front];
    }

    // 出队列
    public int poll() {
        int peek = peek();
        // 头队列后移
        front = (front + 1) % capacity();
        size--;
        return peek;
    }

    // 获取队列长度
    public int size() {
        return size;
    }

    // 判断是否是空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 判断是否已满
    public boolean isFull() {
        return nums.length == size();
    }
}